package org.ala.tiktools.pacemaker.commons;

import java.util.*;

/**
 * @author ala
 * @date 2024-12-18 23:00
 */
public class MathUtils {


    /**
     *  求最大公约数，和几个最大值
     */
    public static int[] gcdAndMax(List<Integer> nums) {
        int gcd = -1, mx = -1;
        for (int n : nums) {
            mx = Math.max(mx, n);
            if (gcd < 0) {gcd = n;}
            else {
                gcd = gcd(gcd, n);
            }
        }
        return new int[]{gcd, mx};
    }
    /**
     *  求最大公约数
     *  <p> stein算法
     */
    public static int gcd(int a, int b) {
        if (a == 0) {return b;}
        if (b == 0) {return a;}

        //  a偶b偶，可以提取个2出来
        if ((a&1) == 0 && (b&1) == 0) {
            return gcd(a>>1, b>>1) << 1;
        }
        //  a偶b奇，a可以先/2，反正2已经不是最大公约数
        else if ((a&1) == 0 && (b&1) == 1) {
            return gcd(a>>1, b);
        }
        //  a奇b偶同理
        else if ((a&1) == 1 && (b&1) == 0) {
            return gcd(a, b>>1);
        }
        //  a奇b奇，gcd = gcd(|a - b|, min(a,b))
        else {
            int diff = -1, mn = -1;
            if (a > b) {
                diff = a - b;
                mn = b;
            } else {
                diff = b - a;
                mn = a;
            }
            return (diff&1) == 0 ? gcd(diff>>1, mn) : gcd(diff, mn);
        }
    }


    static Map<Integer, int[]> factorizeMemo = new HashMap<>();
    /**
     *  分解因子
     */
    public static int[] factorize(int n) {
        int[] res = factorizeMemo.get(n);
        if (res != null) {return res;}

        List<Integer> fs = new ArrayList<>();
        for (int i = 1 ; i*i <= n ; i++) {
            if (n % i == 0) {
                int j = n / i;
                fs.add(i);
                if (i != j) {fs.add(j);}
            }
        }
        res = fs.stream().sorted((i,j) -> i-j).mapToInt(Integer::new).toArray();
        factorizeMemo.put(n, res);
        return res;
    }


    /**
     *  模运算
     *  <p> 暂时没想到什么快速的方法
     */
    public static long mod(long a, long b) {
        return a % b;
    }


}
